前言

昨天提到在 Sutton 的書中，說明 SARSA 比 Q-Learning "保守"，並可以透過 cliff walking 這個例子來說明。今天將會 cliff walking，並實作用這兩個演算法處理 cliff walking 的結果。

cliff walking

中文直接翻譯為「峭壁行走」，與之前提到的 GridWorld 很像，但多了一些設定 (如：避開某些格子不要行走)，這些設定通常會給予大量的負回饋。書上的設定如下：

• 狀態： 4 x 12 格
• 起始狀態：左下角
• 終止狀態：右下角
• 峭壁狀態(給予極大負回饋的狀態)：除了起始與終止狀態，最下方那一列的所有狀態 (上圖灰色 The Cliff 部分)
• 動作集：上、下、左、右
• 獎勵函數：峭壁狀態為 -100，其餘狀態為 -1

這邊我們不使用轉移矩陣，而改用另一個函式達到相同效果：

def TransMat(now_state, action):
    max_row = 4
    max_col = 12
    now_row = int(now_state/max_col)
    now_col = (now_state%max_col)

    if max_col < now_col or max_row < now_row or now_col < 0 or now_row < 0:
        print('index error')
        return

    col = now_col
    row = now_row
    if action == 0 and now_row > 0:
        row -= 1
    elif action == 1 and now_col > 0:
        col -= 1
    elif action == 2 and (max_row-1) > now_row:
        row += 1
    elif action == 3 and (max_col-1) > now_col:
        col += 1
    next_state = row*max_col + col
    return next_state

比較 SARSA 與 Q-Learning

這邊就不詳細介紹實作內容(ex: SARSA, Q-Learning, 更新方法...等)，前幾天就有說明了。參數的部分，兩個方法使用的參數完全一致，詳細的設定可以到 GitHub 查看。這邊說明我們要怎麼比較 SARSA 與 Q-Learning 方法。

比較 Episode 的回饋

上述 cliff walking 的設定中，除了 cliff 外的狀態，都是 -1。換句話說，我們可以透過觀察每個 episode 的狀態，大致觀察每次 episode 中的移動有沒有效率、表現得好不好。如果有效率的話，該 episode 的整體回饋會接近 0，反之則會很大。結果如下圖所示：

左邊這張圖，是使用 SARSA 方法得到的 episode reward，右邊則是使用 Q-Learning 方法。episode reward 的計算方法，是將單次 episode 中，所有的回饋加總而得。

[SARSA episode reward]
[Q-Learning episode reward]
[plot script]

觀察結果

這邊我們可以觀察到兩個現象：

• 在初期，Q-Learning 常有一些得分特別高的值，SARSA 則是一值很穩定。
• 在後期，SARSA 慢慢維持在接近 0 的地方，但 Q-Learning 卻動不動就出現 -100 的結果。

從上述的兩個現象，應證了書上寫的「SARSA 比 Q-Learning 來的保守」這件事。至於為什麼會這樣呢？我想明天可以用數學的角度，提供一些可能的思路。